package com.demo.java.OD451_500.OD481;

import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【生成回文素数(E卷-100分)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146407607
 */
public class OdMain {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = Integer.parseInt(in.nextLine()); // 读取输入数字 N
        System.out.println(primePalindrome(n)); // 输出最小回文素数
    }

    // 找到大于 N 的最小回文素数
    public static int primePalindrome(int n) {
        if (n <= 11) {
            // 如果 N 小于或等于 11，直接从 N 开始寻找素数
            int num = n;
            while (!isPrime(num)) {
                num++; // 向上查找下一个素数
            }
            return num;
        }

        int minPrimePalindrome = 0;
        int left = 10; // 从 10 开始生成回文数

        // 不断生成回文数，直到找到一个素数
        while (minPrimePalindrome == 0) {
            int palindrome = generatePalindrome(left);
            if (palindrome >= n && isPrime(palindrome)) {
                minPrimePalindrome = palindrome; // 找到符合条件的回文素数
            } else {
                left++; // 增大左半部分，生成下一个回文数
            }
        }
        return minPrimePalindrome; // 返回找到的回文素数
    }

    // 判断一个数是否是素数
    public static boolean isPrime(int num) {
        if (num == 1) {
            return false; // 1 不是素数
        }
        if (num % 2 == 0) {
            return num == 2; // 2 是唯一的偶数素数
        }
        // 判断是否有其他因数
        for (int i = 3; i * i <= num; i += 2) {
            if (num % i == 0) {
                return false; // 有其他因数，返回 false
            }
        }
        return true; // 无其他因数，返回 true
    }

    // 根据左半部分生成回文数
    public static int generatePalindrome(int left) {
        int palindrome = left;
        left /= 10; // 去掉最后一位数字
        // 反转左半部分并添加到右边
        while (left > 0) {
            palindrome = palindrome * 10 + left % 10;
            left /= 10;
        }
        return palindrome; // 返回生成的回文数
    }
}